Masala #0653

Xotira 10 MB Vaqt 300 ms Qiyinchiligi 20 %

Kvadrat

Dekart koordinatalar tizimida 4 ta d₁, d₂, d₃, d₄ (d_i = (x,y)) nuqta beriladi.

Bu nuqtalardan kordinata o'qlariga paralel bolgan to'g'ri tortburchak bolishi kafolatlanadi. Siz istalgan d_i= (x, y) nuqtani (x,y+1), (x,y−1), (x+1,y) va (x−1,y) nuqtalardan biriga siljitishingiz mumkin boladi. Vazifangiz OX va OY oqlariga paralel bo'lgan kvadrat hosil qilish uchun minimum urinishlarda sonini topishdan iborat.

Berilgan nuqtalar 1 bir xil bo'lmasligi taminlanadi.

Kiruvchi ma'lumotlar:

INPUT.TXT Kiritish faylida 1-qatorda bitta butun son t (1 ≤ t ≤ 10⁴) - test soni.

har bir test uchun 4ta (d_i = (x,y)) nuqta kordinatalari kiritiladi.Har bir satrda ikkita butun son x va y (0 ≤ x,y ≤ 10⁹).

Chiquvchi ma'lumotlar:

OUTPUT.TXT Chiqish faylida Kvadrat olish uchun zarur bo'lgan minimal qadamlar sonini har bir test uchun alohida qatorlarda chop eting.

Misollar

#	input.txt	output.txt
1	3 0 2 4 2 2 0 2 4 1 0 2 0 4 0 6 0 1 6 2 2 2 5 4 1	8 7 5

Izoh:

1-test uchun minimal urinishlar soni quydagicha bo'lishi mumkin:

Har bir nuqta ikki marta siljiydi, shuning uchun natija 2+2+2+2=8.
Ikkinchi to'plamda optimal javoblardan biri quyida tasvirlangan:

Natija : 3+1+0+3=7.
Uchinchi to'plamda optimal yurishlardan biri quyida tasvirlangan:

Natija : 1+1+2+1=5.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin